//n皇后问题

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {

  

    /**
     * 
     * @param {Set} row 
     * @param {Set} col 
     * @param {Number} i 
     * @param {Number} j 
     */
    function inALine(row,col,i,j,map){
        if(col.has(j)) return false
        let r = i
        let c = j
        while(r<n&&c<n){
            if(map[r][c]==='Q') return false 
            r++
            c++
        }
        r = i
        c = j
        while(r>=0&&c>=0){
            if(map[r][c]==='Q') return false 

            r--
            c--
        }
        r = i
        c = j
        while(r<n&&c>=0){
            if(map[r][c]==='Q') return false 

            r++
            c--
        }
        r = i
        c = j
        while(r>=0&&c<n){
            if(map[r][c]==='Q') return false 

            r--
            c++
        }
        return true
    }

    /**
     * 
     * @param {Set} row 
     * @param {Set} col 
     * @param {String[][]} map 
     * @param {Number} x
     */
    function search(row,col,map,x){
        if(x>=n){
            if(row.size===n&&col.size===n){
                ans.push(JSON.parse(JSON.stringify(map)))
            }
            return
        }
        row.add(x)
            for(let j=0;j<n;j++){
                if(inALine(row,col,x,j,map)){
                    col.add(j)
                    map[x][j] = 'Q'
                    search(row,col,map,x+1)
                    col.delete(j)
                    map[x][j] = '.'
                }
            }

    }

    const ans = []
    let map = new Array(n)
    for(let i=0;i<n;i++){
        let r = []
        for(let j=0;j<n;j++){
            r.push('.')
        }
        map[i] = r
    }
    let row = new Set()
    let col = new Set()
    search(row,col,map,0)
    let res = []
    for (const it of ans) {
        let a = []
        for(const t of it){
            let s = ''
            for(const p of t){
                s+=p
            }
            a.push(s)
        }
        res.push(a)
    }
    return res
};

const n = 4
const ans =solveNQueens(n)
console.log(ans)